trait SimpleInput { self: SimpleInput with SimpleResults =>
  // The type of the elements consumed by this parser
  type Elem
  type Input
  implicit def InputIsParseInput(in: Input): ParseInput
  trait ParseInput {
  	def first: Elem
    def consumeFirst: Success[Elem]

  	def result[T](r: T): Success[T]
    def failure: Failure
    def error: Error
  }
}

trait SimpleResults { self: SimpleInput with SimpleResults =>
  sealed abstract class Result[+T] {
    def isEmpty: Boolean
    def get: T = Predef.error("Get on empty result")
    def getOrElse[S >: T](default: => S): S = if(isEmpty) default else get

    def next: Input

    // using pattern matching on `this` instead of late-binding for performance...
    def map[U](f: T => U): Result[U] = this match {
      case Success(x, i) => Success(f(x), i)(zero)
      case x : NoSuccess => x // compiler needs the ascription... why?
    } 
  
    def flatMap[U](f: T => Result[U]): Result[U] = this match {
      case Success(x, _) => f(x) //withZero(zero)
      case x : NoSuccess => x
    }
   
    def flatMapInfo[U](f: T => Input => Result[U]): Result[U] = this match {
      case Success(x, i) => f(x)(i) //withZero(zero)
      case x : NoSuccess => x
    } 
  
    // used by filtering
    def zero: NoSuccess    
    def filter(f: T => Boolean): Result[T] = this match {
      case Success(x, _) if !f(x) => zero
      case _ => this
    }
   
    def filterMap[U](f: PartialFunction[T, U]): Result[U] = this match {
      case Success(x, i) if !f.isDefinedAt(x) => zero
      case Success(x, i) => Success(f(x), i)(zero) // TODO: should this be zero?
      case x : NoSuccess => x
    }  
  
    def append[U >: T](alt: => Result[U]): Result[U] = this match {
      case self@Failure(_, _) => alt
      case x => x
    } 
  
    def explain(ei: String) =  this match {
      case Success(x, i) => this
      case Failure(_, i) => Failure(ei, i)
      case Error(_, i) => Error(ei, i)      
    } 

    def matchResult[U >: T](f: (U, Input) => Result[U])(g: (String, Input) => Result[U]) =  this match {
      case Success(x, i) => f(x, i)
      case ns: NoSuccess => g(ns.errMsg, ns.next)
    } 

    def withZero(z: NoSuccess) =  this match {
      case Success(x, i) => new Success(x, i)(z)
      case Failure(ei, i) => new Failure(ei, i){override val zero=z}
      case Error(ei, i) => new Error(ei, i){override val zero=z}   
    } 
  }

  case class Success[+T](override val get: T, next: Input)(val zero: NoSuccess) extends Result[T] {
    def isEmpty = false
  }

  sealed abstract class NoSuccess extends Result[Nothing] {
    def isEmpty = true
    def errMsg: String
    val zero = this
  }

  case class Failure(override val errMsg: String, next: Input) extends NoSuccess 
  case class Error(override val errMsg: String, next: Input) extends NoSuccess 
}

trait SimpleParsers extends SimpleInput with SimpleResults {
  def success[T](v: T): Parser[T] = new Parser[T]{def apply(in: Input)   = in.result(v)}
  def failure: Parser[Nothing] = new Parser[Nothing]{def apply(in: Input)= in.failure} 
  def error: Parser[Nothing] = new Parser[Nothing]{def apply(in: Input)  = in.error}

  def consumeFirst: Parser[Elem] = new Parser[Elem]{def apply(in: Input) = in.consumeFirst}

  def acceptIf(p: Elem => Boolean): Parser[Elem] = consumeFirst filter(p)

  implicit def accept(e: Elem): Parser[Elem] = acceptIf(_ == e).expected(e.toString)
  def accept[ES <% Iterable[Elem]](es: ES): Parser[List[Elem]] = es.foldRight[Parser[List[Elem]]](success(Nil)){(x, pxs) => accept(x) ~ pxs ^^ mkList}

  abstract class Parser[+T] extends (Input => Result[T]) { 
    def apply(in: Input): Result[T]

  // core methods (should coincide with the methods in Iterable when the latter finally abstracts over its type constructor)
    // flatMap handles the plumbing of the state (which includes how much input the parser consumed)
    def flatMap[U](f: T => Parser[U]): Parser[U] 
      = new Parser[U]{def apply(in: Input) = Parser.this(in) flatMapInfo(f)}
          // if we don't back-track, the next parser shouldn't either (note: if we do backtrack, that does not mean the next one should also)

    def map[U](f: T => U): Parser[U] //= flatMap{x => success(f(x))}
      = new Parser[U]{def apply(in: Input) = Parser.this(in) map(f)}
    
    def filter(f: T => Boolean): Parser[T] // = flatMap{x => if(f(x)) success(x) else nosuccess }
      = new Parser[T]{def apply(in: Input) = Parser.this(in) filter(f)}
    
    def filterMap[U](f: PartialFunction[T, U]): Parser[U] // = flatMap{x => if(f.isDefinedAt(x)) success(f(x)) else nosuccess }
      = new Parser[U]{def apply(in: Input) = Parser.this(in) filterMap(f)}
        
    // the lazy version of ++ 
    def append[U >: T](p: => Parser[U]): Parser[U] 
      = new Parser[U]{def apply(in: Input) = Parser.this(in) append p(in)}
  
  // specialised sequencing
    def ~ [U](p: => Parser[U]): Parser[~[T, U]] = for(a <- this; b <- p) yield new ~(a,b)
    // see comment at end of file for the derivation of the expansion of ~
  
    def ~> [U](p: => Parser[U]): Parser[U] = for(a <- this; b <- p) yield b
    def <~ [U](p: => Parser[U]): Parser[T] = for(a <- this; b <- p) yield a

  // error-reporting    
    // if the parser is not successful at input `in`, set the `errMsg` to `msg(in)`
    def explainWith(msg: Input => String): Parser[T] =  new Parser[T]{def apply(in: Input) : Result[T] = 
      Parser.this(in) explain msg(in)
    }
  
    def explain(msg: String): Parser[T] =  new Parser[T]{def apply(in: Input) : Result[T] = 
      Parser.this(in) explain msg
    }

    def expected(kind: String): Parser[T] = explainWith{in => ""+ kind +" expected, but \'"+ in.first +"\' found."}
  
  // shortcuts:
    def | [U >: T](q: => Parser[U]): Parser[U] = append(q)
    def ^^ [U](f: T => U): Parser[U] = map(f)
    def ^^^ [U](f:  U): Parser[U] = map(x => f)
    def >>[U](f: T => Parser[U]) = flatMap(f)
  }  

  def opt[T](p: => Parser[T]): Parser[Option[T]] = p ^^ {x => Some(x)} | success(None)

  def rep[T](p: => Parser[T]): Parser[List[T]] 
    = rep1(p) | success(List())

  def rep1[T](p: => Parser[T]): Parser[List[T]] 
    = rep1(p, p)
  
  def rep1[T](first: => Parser[T], p: => Parser[T]): Parser[List[T]] 
    = first ~ rep(p) ^^ mkList

  def chainl1[T](p: => Parser[T], q: => Parser[(T, T) => T]): Parser[T] 
    = p ~ rep(q ~ p) ^^ {case x ~ xs => xs.foldLeft(x)((a, f_b) => f_b._1(a, f_b._2))}  // ((a, {f, b}) => f(a, b))
  
  def chainl1[T, U](first: => Parser[T], p: => Parser[U], q: => Parser[(T, U) => T]): Parser[T] 
    = first ~ rep(q ~ p) ^^ {
        case x ~ xs => xs.foldLeft(x){(_, _) match {case (a, (f, b)) => f(a, b)}}
      }

  def log[T](p: => Parser[T])(name: String): Parser[T] = new Parser[T]{
    def apply(in: Input) : Result[T] = {
      println("trying "+ name +" at \'"+ in + "\'")
      val r = p(in)
      println(name +" --> "+ r)
      r
    }
  }

  def mkList[T] = (_: ~[T, List[T]]) match { case x ~ xs => x :: xs }
  case class ~[+a, +b](_1: a, _2: b) {
    override def toString = "("+ _1 +" ~ "+ _2 +")"
  }
}

trait StringParsers extends SimpleParsers {
  type Elem = Char
  type Input = String
  val EOI = 0.toChar
  
  implicit def InputIsParseInput(self: Input): ParseInput = new ParseInput {
    val chars = self.toList
    
  	def first: Elem = if(chars.isEmpty) EOI else chars(0)
  	def rest: String = if(chars.isEmpty) "" else chars.tail.mkString("")
    def consumeFirst: Success[Elem] = Success(first, rest)(Failure("zero", self)) 

  	def result[T](r: T): Success[T] = Success(r, self)(Failure("zero", self))
    def failure: Failure = Failure("unknown failure", self)
    def error: Error = Error("unknown error", self)
  } 
  
  def eoi = accept(EOI) expected("end of input")
}

trait Syntax {
  class Term
	case class Var(name: String) extends Term
	case class Abs(name: String, body: Term) extends Term
	case class App(fun: Term, arg: Term) extends Term
}

object LambdaParser extends StringParsers with Syntax {
  def letter = log(acceptIf(_.isLetter) expected("letter"))("letter")
  def digit = log(acceptIf(_.isDigit) expected("digit"))("digit")
  def ws = log(rep1(accept(' ')) expected("whitespace"))("ws")
  
  def ident = log((((letter ~ rep(letter | digit)) ^^ mkList) ^^ {x => x.mkString("")}) expected("identifier"))("ident")
  def term = chainl1(termSingle, ws ^^^ (App(_: Term, _: Term)))    
  def termSingle: Parser[Term] = log( 
    ( (accept("\\") ~> ident_ws) ~ ('.' ~> term_ws) ^^ {case x ~ body => Abs(x, body)  }
    | ident                     ^^ {case x => Var(x)} 
    ))("term")
    
  def term_ws = opt(ws) ~> term <~ opt(ws)
  def ident_ws = opt(ws) ~> ident <~ opt(ws)
    
  def main(args: Array[String]) = println((term <~ eoi)(args(0)))
}